// 给定整数数组arr，再给定一个整数k，要求返回数组arr中最小的k个数

// 思路1： 堆排序（基于大顶堆）
// 具体做法：
// 1. 使用数组前k个元素，维护一个大小为k的大顶堆
// 2. 遍历数组[k, size - 1], 判断其与堆顶元素的关系，如果遇到比堆顶元素小的元素
//  则将与堆顶元素进行交换，再将这k个元素调整为大顶堆
// 3. 最后输出大顶堆的k个元素

// 时间复杂度：O(nlogk)
// 空间复杂度：O(1)

function heapify(nums, index, end) {
    let left = 2 * index + 1
    let right = left + 1
    while (left <= end) {
        let max_index = index
        if (nums[left] > nums[max_index]) {
            max_index = left
        }
        if (right <= end && nums[right] > nums[max_index]) {
            max_index = right
        }
        if (index === max_index) {
            break
        }
        [nums[index], nums[max_index]] = [nums[max_index], nums[index]]
        index = max_index
        left = 2 * index + 1
        right = left + 1
    }
}

function buildMaxHeap(nums, k) {
    // ( k - 2 ) / 2是最后一个非叶子节点，叶子节点不用调整
    for (let i =  Math.floor((k - 2) / 2); i >= 0; i--) {
        heapify(nums, i, k - 1)
    }
}

function getLeastNumbers(arr, k) {
    let size = arr.length
    if (k <= 0 || !arr) {
        return []
    }
    buildMaxHeap(arr, k)
    for (let i = k; i < size; i++) {
        if (arr[i] < arr[0]) {
            [arr[i], arr[0]] = [arr[0], arr[i]]
            heapify(arr, 0, k - 1)
        }
    }
    return arr.slice(0, k)
}

let arr = [3, 8, 5, 4, 7, 9, 2, 1]
let k = 2
console.log(getLeastNumbers(arr, k))
// 思路2： 快速排序
// 使用快速排序在每次调整时，都会确定一个元素的最终位置，且以该元素为界限，将数组分为左右两个子数组
// 左子数组中的元素都比该元素小，右子树组中元素都比该元素大
// 只要某次划分恰好是第k个元素下标，就找到了数组中最小的k个数对应的区间，即[0, k-1]

// 时间复杂度：O(n)
// 空间复杂度：O(logn)

function quickSort(arr, low, high, k) {
    let size = arr.length
    if (low < high) {
        let pi = randomPartition(arr, low, high)
        if (pi === k) {
            return arr.slice(0, k)
        }
        if (pi > k) {
            quickSort(arr, low, pi - 1, k)
        }
        if (pi < k) {
            quickSort(arr, pi + 1, high, k)
        }
    }
    return arr.slice(0, k)
}

function randomPartition(arr, low, high) {
    let i = Math.floor(Math.random() * (high - low)) + low;
    [arr[i], arr[low]] = [arr[low], arr[i]]
    return partition(arr, low, high)
}

function partition(arr, low, high) {
    let pivot = arr[low]
    let i = low + 1

    for (let j = i; j <= arr.length; j++) {
        if (arr[j] < pivot) {
            [arr[i], arr[j]] = [arr[j], arr[i]]
            i += 1
        }
    }
    [arr[i - 1], arr[low]] = [arr[low], arr[i - 1]]
    return i - 1
}

function getLeastNumbers2(arr, k) {
    let size = arr.length
    if (k >= size) {
        return arr
    }
    return quickSort(arr, 0, size - 1, k)
}

let arr1 =  [3, 8, 5, 4, 7, 9, 2, 1]
let k1 = 2
console.log(getLeastNumbers2(arr1, k1));
